import java.util.Arrays;
import java.util.Random;
import java.util.SortedMap;

public class Main {
    private int j;

    //    选择排序
//    0 5 9 2 4 7 3 8 1 6
//    0 1 9 2 4 7 3 8 5 6
//    0 1 2 9 4 7 3 8 5 6
//    0 1 2 3 4 7 9 8 5 6
//    0 1 2 3 4 7 9 8 5 6
//    0 1 2 3 4 5 9 8 7 6
//    0 1 2 3 4 5 6 8 9 7
//    0 1 2 3 4 5 6 8 7 9
//    0 1 2 3 4 5 6 7 8 9
// 插入排序
    public int[] InsertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[i] < arr[i - 1]) {
//                    交换
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
        return arr;
    }

    public int[] SelectionSort(int[] arr) {
        for (int j = 0; j < arr.length - 1; j++) {
            int min = arr[j];
            int minIndex = j;
            for (int i = j; i < arr.length; i++) {
                if (arr[i] < min) {
                    min = arr[i];
                    minIndex = i;
                }

            }
            if (minIndex != j) {
                int temp = arr[j];
                arr[j] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
        return arr;
    }
    public static void main(String[] args) {
        // 创建一个长度为100的数组
        int[] array = new int[100];
        // 创建Random对象用于生成随机数
        Random random = new Random();

        // 填充数组，范围为1到1000
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(1000) + 1; // 生成1到1000的随机数
        }

        // 打印数组内容
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println(Arrays.toString(array));
        Main sort = new Main();
        System.out.println(Arrays.toString(sort.InsertionSort(array)));
        System.out.println(Arrays.toString(sort.SelectionSort(array)));
    }
}
